#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param matrix: A list of lists of integers
    @param target: An integer you want to search in matrix
    @return: An integer indicate the total occurrence of target in the given matrix
    """
    def searchMatrix(self, matrix, target):
        if not matrix:
            return 0

        self.rows, self.cols = len(matrix), len(matrix[0])
        self.target = target
        self.matrix = matrix
        self.cnt = 0

        self.search(0, 0, self.rows-1, self.cols-1)
        return self.cnt

    def search(self, x_row, x_col, y_row, y_col):
        # assert x_row <= y_row
        # assert x_col <= y_col
        if x_row > y_row:
            return
        if x_col > y_col:
            return

        x = self.matrix[x_row][x_col]
        y = self.matrix[y_row][y_col]

        if self.meet(x_row, x_col, y_row, y_col):
            if x == self.target:
                self.cnt += 1
            return

        if not (x <= self.target <= y):
            return

        idxs = self.matrix_idx_split(x_row, x_col, y_row, y_col)
        for idx in idxs:
            self.search(*idx)

    def matrix_idx_split(self, x_row, x_col, y_row, y_col):
        # (1, 2) ------> 1, 2
        # (2, 3) ------> 2, 3

        mid_row = (x_row + y_row) // 2
        mid_col = (x_col + y_col) // 2

        i1 = (x_row, x_col, mid_row, mid_col)
        i2 = (mid_row+1, mid_col+1, y_row, y_col)

        i3 = (x_row, mid_col+1, mid_row, y_col)
        i4 = (mid_row+1, x_col, y_row, mid_col)

        return i1, i2, i3, i4

    def meet(self, x_row, x_col, y_row, y_col):
        return (x_row, x_col) == (y_row, y_col)


def test():
    l = [
        [1, 3, 5, 7],
        [2, 4, 7, 8],
        [3, 5, 9, 10]
    ]

    s = Solution()
    r = s.searchMatrix(l, 3)
    print(r)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
